There are many known ways to protect data communications between two parties. For example, the Secure Internet Protocol (IPSec) standards may be used, as defined in the Internet Drafts that are available at the “html.charters/ipsec-charter.html” document of the Internet Engineering Task Force Web site at “ietf” dot “org”. IPSec implementation is generally described in the latest version of the “Security Architecture for the Internet Protocol” Internet Draft (draft-ietf-arch-sec-xx.txt). An earlier version of IPSec is described in RFCs 1825 through 1829.
Numerous firewall products, such as Cisco IOS and Cisco PIX Firewall, support the IPSec standards. However, protection of communication among multiple parties is a more difficult problem and there are fewer established solutions.
Achieving secure multi-party communication has become more important as more multimedia information has begun to move across public data networks. Video and audio traffic consumes far more resources, such as bandwidth, buffer space, and processing power, than conventional data traffic. To avoid congestion at traffic routing points and reduce processing load at data sources, multicasting is often used to efficiently deliver traffic to a group of nodes. Secure communication is a requirement for network services that use multicasting, such as confidential tele-conferencing, broadcasting customer information, and distribution of video to subscribers.
In one security approach, each data packet in a multicast session is encrypted at the data source with a security key that is shared by all group members. For the purpose of efficiency, members who are participating in a multicast group are required to use the same session key to decrypt data packets that carry the multicast information. This approach is used because it requires each data packet to be encrypted only once. The encrypted packet is then delivered to each group member, which uses the same key to decrypt the packet.
During the course of the multicast, group members may join or depart, resulting in re-formation of the group. To ensure that departed group members cannot continue to obtain multicast information, and to ensure that joining group members can, establishment of a new shared session key for use by the re-formed group is required. Thus, an important technical problem involves how to establish and re-establish a shared session key for communication among all participants.
Among two parties, “pairwise” session keys can be negotiated either through a trusted agent or directly between the two participants. When negotiation occurs through a trusted agent, a public key exchange can be used, such as Diffie-Hellman key exchange. Each participant establishes a secure channel with the trusted agent and negotiates or retrieves the pairwise session key over the secure channel. When negotiation occurs directly between two participants, several approaches may be used. A public key exchange may be used; alternatively, a pre-determined secret “mega” key is shared by the parties and used in periodic re-negotiation of pairwise session keys.
These approaches can be applied to multi-party key negotiation. In one application, each of the members of a multicast group establishes a different pairwise key with a group controller. As a result, each group member sets up a different secure communication channel with the group controller. Thereafter, group members can negotiate and re-negotiate new session keys with the group controller using their respective secure communication channels.
For example, pairwise keys are negotiated between a session controller node and all participants in H. Harney et al., “Group Key Management Protocol Architecture, RFC 2094, September 1994, and H. Harney et al., “Group Key Management Specification,” RFC 2093, September 1994. In D. Wallner et al., “Key Management for Multicast: Issues and Architectures, RFC 2627, June 1999, additional keys are used to form a logical hierarchy of secure communication, where the session controller can use a single key to talk to a sub-group of participants. In H. Harney et al., “Group Secure Association Key Management Protcool,” Internet-Draft “draft-harney-sparta-gsakmp-sec-02.txt,” June 2000, the underlying Security Associations (SA's) between the group controller and the members are assumed to exist. The SA's are established by protocols such as ISAKMP, IPSec, etc., and use pairwise shared keys.
Further, in T. Hardjono et al., “Intra-Domain Group Key Management Protocol,” Internet-Draft “draft-ietf-ipsec-intragkm-02.txt,” February 2000, the group key is delivered using a two-level hierarchy. Each participant is assumed to have established an SA and a shared key with an Area Key Distributor (AKD) of the area in which the participant resides, and each AKD is assumed to have established an SA and a shared key with the Domain Key Distributor (DKD), which is the root of the hierarchy. The approach in S. Setia et al., “Kronos: A Scalable Group Re-Keying Approach for Secure Multicast,” Proc. Of 2000 IEEE Symposium on Security and Privacy, 2000, has similar requirements. In H. Harney et al., “Group Key Management Protocol (GKMP) Architecture,” RFC 2094, July 1997, secure pairwise communication is assumed for the distribution of a group key.
Thus, while many approaches for two-party key negotiation have been extended for use in multi-party key negotiation, they all require generating pairwise keys to establish a secure communication channel for key negotiation traffic. There is a need for a way to negotiate and re-negotiate session keys among multiple parties using an insecure channel. An example of an insecure channel is a public network or group of internetworks, such as the global packet-switched internetworks known as the Internet.
Diffie-Hellman key exchange is widely used to negotiate keys among two parties over an insecure channel, as described in W. Diffie et al., “New Directions in Cryptography,” IEEE Transactions on Information Theory, pp. 644–654, November 1976. However, Diffie-Hellman key exchange is difficult to implement in a distributed environment that includes a large group of participants. It requires a node to send a control message to traverse all participants in older to accumulate local random numbers in the exponent of its calculation. When the control message arrives back, the node can compute the shared key. If all nodes follow the same approach, all will have the same key, and the control messages can be sent in the clear.
Unfortunately, the processing overhead involved in this approach, based on the number of messages that must be dispatched to arrive at a shared key, is very high. One known implementation has a complexity of O(|M|2) with respect to computation or communication, where |M| is the size of the communication group M; this is far higher than the complexity O(|M|) of the established protocols described above.
Based on the foregoing, there is a clear need to negotiate and re-negotiate session keys over a non-secure channel among a large number of multicast group participants in a way that is computationally efficient.